home *** CD-ROM | disk | FTP | other *** search
/ Aminet 5 / Aminet 5 - March 1995.iso / Aminet / dev / misc / LEDA_gene.lha / LEDA-3.1c-generic / man / partition.tex < prev    next >
Encoding:
Text File  |  1994-08-05  |  1.9 KB  |  60 lines
  1. {\magonebf 3.10 Partitions (partition)}
  2.  
  3. {\bf 1. Definition}
  4.  
  5. An instance of the data type $partition$ consists of a finite set of 
  6. items (predefined type $partition\_item$) and a partition of this set 
  7. into blocks.
  8.  
  9.  
  10. \def\name{$partition$}
  11. \def\type{partition}
  12.  
  13. \bigskip
  14. {\bf 2. Creation}
  15.  
  16. \create P {}
  17.  
  18. Creates an instance $P$ of type $partition$ and initializes it to the empty 
  19. partition. 
  20.  
  21.  
  22.  
  23. \bigskip
  24. {\bf 2. Operations}
  25.  
  26. \+\cleartabs & \hskip 3.2truecm & \hskip 4.8truecm &\cr
  27. \+\op partition\_item make\_block {}
  28.                              {returns a new $partition\_item$ $it$ and adds}
  29. \+\nop                       {the block $\{it\}$ to partition $P$.}
  30. \smallskip
  31. \+\op partition\_item find {partition\_item\ p} {}
  32. \+\nop                      {returns a canonical item of the block that}
  33. \+\nop                      {contains item $p$, i.e., if $P$.same\_block($p,q$)}
  34. \+\nop                      {then $P$.find($p$) = $P$.find($q$).}
  35. \+\nop                      {\precond{$p$ is an item in $P$.}}
  36. \smallskip
  37. \+\op bool            same\_block {partition\_item\  p,\ partition\_item\ q} {}
  38. \+\nop                       {returns true if $p$ and $q$ belong to the same}
  39. \+\nop                       {block of partition $P$.}
  40. \+\nop                       {\precond{$p$ and $q$ are items in $P$.}}
  41. \smallskip
  42. \+\op void            union\_blocks {partition\_item\ p,\ partition\_item\ q} {}
  43. \+\nop                       {unites the blocks of partition $P$ containing}
  44. \+\nop                       {items $p$ and $q$.}
  45. \+\nop                       {\precond{$p$ and $q$ are items in $P$.}}
  46.  
  47.  
  48. \bigskip
  49. {\bf 3. Implementation}
  50.  
  51. Partitions are implemented by the union find algorithm with weighted union
  52. and path compression (cf.~[T83]).  Any sequence of $n$ make\_block and 
  53. $m \ge n$ other operations takes time $O(m\alpha(m,n))$.
  54.  
  55.  
  56. \bigskip
  57. {\bf 4. Example }
  58.  
  59. Spanning Tree Algorithms (cf.~graph)
  60.